#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <sys/time.h>
#include <upc.h>
#include <math.h>
#include <assert.h>

//#define DEBUG


//
// auxiliary functions
//
inline int max( int a, int b ) { return a > b ? a : b; }
inline int min( int a, int b ) { return a < b ? a : b; }
inline int ceiling (int a, int b) { return (int)( ceil((float)a/(float)b)); }

//these set the problem size
static int capacity;
static int nitems;
static int nElem;   

double read_timer( )
{
    static int initialized = 0;
    static struct timeval start;
    struct timeval end;
    if( !initialized )
    {
        gettimeofday( &start, NULL );
        initialized = 1;
    }
    gettimeofday( &end, NULL );
    return (end.tv_sec - start.tv_sec) + 1.0e-6 * (end.tv_usec - start.tv_usec);
}

// Computes a single block, and saves the result in RESULT
// Assume that RESULT is at least nElem elements long
// REMEMBER: This is computation is performed by the thread in-charge of A_xy for the row below it.
// We DO NOT change anything in the current block.
// Returns the number of elements copied to the RESULT array
int compute_A_xy (int x, int y, int *result, shared int *T, shared int* w, shared int*v) {

    int wx = w[x+1];
    int vx = v[x+1];

    // The boundaries of the actual block, in the 2D table [y_begin ... y_end] 
    // These are defined by the Y value alone
    int y_begin = y*nElem;
    int y_end = (((y+1)*nElem-1)>capacity) ? capacity : ((y+1)*nElem-1);

    for (int i=y_begin; i<=y_end; i++) {
        if (i<wx) result[i-y_begin] = T[(x*(capacity+1))+i];
        else result[i-y_begin] = max (T[(x*(capacity+1))+i], T[(x*(capacity+1))+i-wx]+vx);
    } 
    // Finished
    return (y_end-y_begin+1);
}


//
//  solvers
//
int build_table( int nitems, int cap, shared int *T, shared int *w, shared int *v )
{

    if (MYTHREAD == 0) {
        int w0 = w[0];
        int v0 = v[0];
        // Fill in the first row, shall we?
        for (int i=0; i<=capacity; i++) {
            if (i<w0) T[i] = 0;
            else T[i] = v0;
        }
    }

    // The table below shows what Thread is computing a temporary block USING what block at what step.
    // For example, if Thread #0 in step #0 is calculating something USING A_00, and putting that in 
    //      a temporary array. This temporary array will be used to calculate A_10
    // Easy way to remember: x+y = step 

    //  0       1       2       3       4       5       6       7       8       9       10
    //  A_00    A_01    A_02    A_03    A_40    A_41    A_42    A_43    xxx     xxx     xxx
    //  xxx     A_10    A_11    A_12    A_13    A_50    A_51    A_52    A_53    xxx     xxx
    //  xxx     xxx     A_20    A_21    A_22    A_23    A_60    A_61    A_62    A_63    xxx
    //  xxx     xxx     xxx     A_30    A_31    A_32    A_33    A_70    A_71    A_72    A_73


    for (int step=0; step < nitems-2+THREADS; step++) {

        int x = ((step-MYTHREAD)/THREADS)*THREADS + MYTHREAD;
        int y = step - x;
    
        // This condition says if we are to do some real work or not
        // Basically representing those 'xxx's in the table
        int conditional = !((step < MYTHREAD) || (x>=nitems-1));

        //int result[nElem];
        int result[10000];     // bupc requires the size to be known at compile time
        int temp=0;

        if (conditional) 
            temp = compute_A_xy(x, y, result, T, w, v);
        upc_barrier;
   
        // Now these results need to be pushed to the next row.
        // For example, A_xy needs to be pushed to A_(x+1)y
        // BUT, only if we did compute anything AND, we are still
        // writing to the T table (and not corrupting stuff)
        if (conditional) {
            int t = ((x+1)*(capacity+1))+(y*nElem);
            for (int i=0; i<temp; i++) {
               T[t+i] = result[i]; 
            }
        }
        upc_barrier;   

    }

#ifdef DEBUG
    if (MYTHREAD == 0) {
        for (int i=0; i<nitems; i++) {
            for (int j=0; j<(capacity+1); j++) {
                printf("%d\t", T[i*(capacity+1) + j]);
            }
            printf("\n");
            fflush(stdout);
        } 
    }
    upc_barrier;  
#endif   

 
    return T[nitems*(capacity+1) -1];
}

void backtrack( int nitems, int cap, shared int *T, shared int *w, shared int *u )
{
    int i, j;

    if( MYTHREAD != 0 )
        return;

    i = nitems*(cap+1) - 1;
    for( j = nitems-1; j > 0; j-- )
    {
        u[j] = T[i] != T[i-cap-1];
        i -= cap+1 + (u[j] ? w[j] : 0 );
    }
    u[0] = T[i] != 0;
}

//
//  serial solver to check correctness
//
int solve_serial( int nitems, int cap, shared int *w, shared int *v )
{
    int i, j, best, *allocated, *T, wj, vj;

    //alloc local resources
    T = allocated = malloc( nitems*(cap+1)*sizeof(int) );
    if( !allocated )
    {
        fprintf( stderr, "Failed to allocate memory" );
        upc_global_exit( -1 );
    }

    //build_table locally
    wj = w[0];
    vj = v[0];
    for( i = 0;  i <  wj;  i++ ) T[i] = 0;
    for( i = wj; i <= cap; i++ ) T[i] = vj;
    for( j = 1; j < nitems; j++ )
    {
        wj = w[j];
        vj = v[j];
        for( i = 0;  i <  wj;  i++ ) T[i+cap+1] = T[i];
        for( i = wj; i <= cap; i++ ) T[i+cap+1] = max( T[i], T[i-wj]+vj );
        T += cap+1;
    }
    best = T[cap];
#ifdef DEBUG
    for (int i=0; i<nitems; i++) {
        for (int j=0; j<(capacity+1); j++) {
            printf("%d\t", allocated[i*(capacity+1) + j]);
        }
        printf("\n");
    } 
#endif
    //free resources
    free( allocated );

    return best;
}

//
//  benchmarking program
//
int main( int argc, char** argv )
{
    if (argc == 3) {
        capacity = atoi(argv[1]);
        nitems = atoi(argv[2]);
    } else {
        fprintf(stderr, "You need to specify the problem size like this:\n");
        fprintf(stderr, "%s <capacity> <nitems>\n", argv[0]);
        upc_global_exit(-1);
    }
    nElem = ceiling (capacity+1, THREADS);

    int i, best_value, best_value_serial, total_weight, nused, total_value;
    double seconds;
    shared int *weight;
    shared int *value;
    shared int *used;
    shared int *total;

    //these constants have little effect on runtime
    int max_value  = 1000;
    int max_weight = 1000;


    unsigned int seed = (unsigned int) time (NULL);
    srand48( seed + MYTHREAD );

    //allocate distributed arrays, use cyclic distribution
    weight = (shared int *) upc_all_alloc( nitems, sizeof(int) );
    value  = (shared int *) upc_all_alloc( nitems, sizeof(int) );
    used   = (shared int *) upc_all_alloc( nitems, sizeof(int) );
    // Changing total allocation so that each row of the table is affined to one processing element.
    total  = (shared int *) upc_all_alloc( nitems, (capacity+1)*sizeof(int) );
    if( !weight || !value || !total || !used )
    {
        fprintf( stderr, "Failed to allocate memory" );
        upc_global_exit( -1 );
    }

    // init
    max_weight = min( max_weight, capacity );//don't generate items that don't fit into bag
    upc_forall( i = 0; i < nitems; i++; i )
    {
        weight[i] = 1 + (lrand48()%max_weight);
        value[i]  = 1 + (lrand48()%max_value);
    }

    upc_barrier;

    // time the solution
    seconds = read_timer( );

    best_value = build_table( nitems, capacity, total, weight, value );
    backtrack( nitems, capacity, total, weight, used );
    upc_barrier;

    seconds = read_timer( ) - seconds;

    // check the result
    if( MYTHREAD == 0 ) {
 
        printf("Seed used: %d\n", seed);
        printf( "%d items, capacity: %d, time: %g\n", nitems, capacity, seconds );

        best_value_serial = solve_serial( nitems, capacity, weight, value );
        printf("Serial value: %d, Our value: %d\n", best_value_serial, best_value);

        total_weight = nused = total_value = 0;
        for( i = 0; i < nitems; i++ )
            if( used[i] )
            {
                nused++;
                total_weight += weight[i];
                total_value += value[i];
            }

        printf( "%d items used, value %d, weight %d\n", nused, total_value, total_weight );

        if( best_value != best_value_serial || best_value != total_value || total_weight > capacity ) {
            printf("WRONG SOLUTION\n" );
        }

        //release resources
        upc_free( weight );
        upc_free( value );
        upc_free( total );
        upc_free( used );
    }
    return 0;
}
